/**
 * @file     mergeIntervals.js
 * @brief    [56. 合并区间](https://leetcode.cn/problems/merge-intervals/description/)
 * @author   Zhu
 * @date     2023-06-15 23:27
 */

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
    intervals.sort((a, b) => a[0] - b[0]);

    const res = [];
    for (const [s, e] of intervals) {
        const item = res.pop();
        if (item) {
            if (item[1] >= s) {
                if (e > item[1]) {
                    // merge
                    item[1] = e;
                }
                res.push(item); // contain
            } else {
                res.push(item, [s, e]); // new
            }
        } else {
            res.push([s, e]); // init
        }
    }

    return res;
};

/**
 * 化Range为Point，排成Line，按照括号开闭匹配的思路来提取Range
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
    const line = [];
    for (const item of intervals) {
        // 0 for start, 1 for end
        line.push([0, item[0]]);
        line.push([1, item[1]]);
    }

    line.sort((a, b) => a[1] - b[1]);

    const res = [];
    let startFrom;
    let startMark = 0;
    let preEnd;
    for (const [mark, value] of line) {
        if (startMark === 0) {
            // start point
            if (preEnd != undefined && value === preEnd) {
                // e.g. `[1, 4] [0, 4]` means the last end point is invalid. backward
                const [s] = res.pop();
                startFrom = s;
            } else {
                startFrom = value;
            }
        }

        if (mark === 0) {
            startMark++;
        } else {
            startMark--;
        }

        if (startMark === 0) {
            // end point, collect range
            res.push([startFrom, value]);
            preEnd = value;
        }
    }

    return res;
};
